////////////////////////////////////////////////////////////////////////////////
// Auteur	: Maxime Vanier et Patrick Losier
// date		: 04/03/2013
//
// description : Implementation de l'algorithme Branch And Bound
///////////////////////////////////////////////////////////////////////////////

#include "Algorithmes.h"
#include "BTS.h"
#include "Timer.h"

const std::string AlgoBranchAndBound::ID_BRANCH_AND_BOUND = "algo_branch_&_bound";

AlgoBranchAndBound::AlgoBranchAndBound()
	: Algo(ID_BRANCH_AND_BOUND)
{
}

AlgoBranchAndBound::~AlgoBranchAndBound()
{
}

int AlgoBranchAndBound::execute(const std::map<int, BTS*>& vBTS, int capacite, std::vector<int>& result)
{
	convertMap2MultiMap(vBTS);
	valeurMax_ = 0;

	timer_.start();
	position_ = mmBTS_.rbegin();
	position_++;
	position_--;
	if(CalculNoeud(capacite,0) == -1)
	{
		return -1;  
	}

	return 0;
}

void AlgoBranchAndBound::convertMap2MultiMap(const std::map<int, BTS*>& mBTS)
{
	mmBTS_.clear();

	std::map<int, BTS*>::const_iterator itBTS = mBTS.begin();
	for (itBTS ; itBTS != mBTS.end() ; itBTS++)
	{
		mmBTS_.insert(std::pair<double, BTS*>(itBTS->second->getRevenuPerCapita(), itBTS->second));
	}

}

int AlgoBranchAndBound::CalculNoeud(int capaciteRestante, int valeurCourante)
{
	timer_.stop();
	if (timer_.getElapsedTimeInMilliSec() > timeout_)
	{
		return -1;
	}

	if(position_ == mmBTS_.rend() || capaciteRestante == 0 )
	{
		if(valeurCourante >valeurMax_)
		{
			valeurMax_ = valeurCourante;
		}		
		return 0;
	}

	double SurestimationBranch = ((position_->first)*capaciteRestante) + valeurCourante;
	int debordementCapacite = capaciteRestante - position_->second->getNbAbonnes();
	int revenueCourant = valeurCourante + position_->second->getRevenu();
	
	if( SurestimationBranch <= (double)valeurMax_)
	{
		return 0;	
	}
		
	position_++;
	std::multimap<double, BTS*> ::const_reverse_iterator tmp = position_;

	if(debordementCapacite >= 0)
	{
		if(CalculNoeud(debordementCapacite,revenueCourant) == -1) //On ne prend pas l'objet courant
		{
			return -1;
		}
	}

	position_ = tmp;
	if(CalculNoeud(capaciteRestante,valeurCourante) == -1) //On ne prend pas l'objet courant
	{
		return -1;
	}

	return 0 ;
}